package lcr;

import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;

public class Test0113 {
    public static void main(String[] args) {
        new Solution0113_1().findOrder(3,new int[][]{{1,0},{2,0},{0,2}});
    }
}

class Solution0113_1 {
    int count=0;
    HashMap<Integer, List<Integer>> map = new HashMap<>();
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        int[] record = new int[numCourses];

        for (int[] prerequisite : prerequisites) {
            List<Integer> list = map.getOrDefault(prerequisite[0], new ArrayList<>());
            list.add(prerequisite[1]);
            record[prerequisite[1]]=-1;
            map.put(prerequisite[0],list);
        }

        int[] ans = new int[numCourses];
        for (int i = 0; i < record.length; i++) {
            int now = record[i];
            if (now ==0) dfs(record,i,ans);
            if (count<0) break;
        }

        return count==numCourses?ans:new int[0];
    }

    public void dfs(int[] record,int now,int[] ans){
        List<Integer> list = map.get(now);
        if (list!=null){
            for (Integer next : list) {
                if (record[next]==1) continue;
                else if (record[next]==0){
                    count=-1;
                    return;
                }

                record[next]=0;
                dfs(record,next,ans);
                if (count<0) return;
            }
        }

        record[now]=1;
        ans[count++]=now;
    }
}
